Back to course home
0% completed
Vote For New Content
LinkedIn Hard
Max Points on a Line (hard)
Solution: Max Points on a Line
Closest Binary Search Tree Value II (hard)
Solution: Closest Binary Search Tree Value II
Word Ladder (hard)
Solution: Word Ladder
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Design Add and Search Words Data Structure (medium)
Problem Statement
Design a data structure that supports the addition of new words and the ability to check if a string matches any previously added word.
Implement the Solution class:
Solution()Initializes the object.void addWord(word)Insertswordinto the data structure, making it available for future searches.bool search(word)Checks if there is any word in the data structure that matchesword. The method returnstrueif such a match exists, otherwise returnsfalse.
Note: In the search query word, the character '.' can represent any single letter, effectively serving as a wildcard character.
Examples
Example 1:
- Input:
["Solution", "addWord", "addWord", "search", "search"] [[], ["apple"], ["banana"], ["apple"], ["......"]] - Expected Output:
[-1, -1, -1, 1, 1] - Justification: After adding the words "apple" and "banana", searching for "apple" will return
truesince "apple" is in the data structure. Searching for "......" will also returntrueas "banana" match the pattern.
Example 2:
- Input:
["Solution", "addWord", "addWord", "search", "search"] [[], ["cat"], ["dog"], ["c.t"], ["d..g"]] - Expected Output:
[-1, -1, -1, 1, 0] - Justification: "c.t" matches "cat" and "d..g" doesn't matches "dog".
Example 3:
- Input:
["Solution", "addWord", "search", "search"] [[], ["hello"], ["h.llo"], ["h...o"]] - Expected Output:
[-1, -1, 1, 1] - Justification: "h.llo" and "h...o" both match "hello".
Constraints:
1 <= word.length <= 25wordinaddWordconsists of lowercase English letters.wordinsearchconsist of '.' or lowercase English letters.- There will be at most 2 dots in word for search queries.
- At most 104 calls will be made to addWord and search.
Try it yourself
Try solving this question here:
Java
Saved to Cloud
. . . .
Solution: Coin Change
Solution: Design Add and Search Words Data Structure
Mark as Completed
On this page
Problem Statement
Examples
Try it yourself